{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 绪论的作业"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2-2\n",
    "当插入排序优于归并排序时，有：\n",
    "$$ 8n^2<64nlgn $$\n",
    "验证得，当$n\\leq43$时不等式成立。所以n是小于等于43的整数时成立。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1.2-3\n",
    "有$$100n^2<2^n$$\n",
    "验证得，当$n\\geq15$时不等成立。所以n最小是15。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1-3\n",
    "程序的代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a_str = input().split\n",
    "v = int(input())\n",
    "a = [float(i) for i in a_str]\n",
    "a.append(None)\n",
    "for i in range(len(a)):\n",
    "    if v == a[i]:\n",
    "        print(i)\n",
    "    if i == len(a)-1:\n",
    "        print(\"NIL\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在每次for循环迭代的开始，v不在A[i...j-1]中.三条必要性质:\n",
    "1. 第一次循环为真\n",
    "2. 若某次迭代之前为真，则下一次迭代还为真\n",
    "3. 结束后会得到问题的答案"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1-4\n",
    "1. 输入：两个n元数组数组A、B\n",
    "2. 输出：一个1+n元数组C，使得C表示的数是A、B表示的数之和   \n",
    "代码如下（算法实验Trilling中的代码）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BigNum //高精度\n",
    "{\n",
    "public:\n",
    "\tint valid_len;\n",
    "\tint data[N];\n",
    "\tinline BigNum() // 初始化0\n",
    "\t\t: valid_len(0)\n",
    "\t{\n",
    "\t\tmemset(data, 0, sizeof(data));\n",
    "\t}\n",
    "\tinline BigNum(int n) //初始化n\n",
    "\t{\n",
    "\t\tmemset(data, 0, sizeof(data));\n",
    "\t\tif (n <= 0)\n",
    "\t\t{\n",
    "\t\t\tvalid_len = 0;\n",
    "\t\t\treturn;\n",
    "\t\t}\n",
    "\t\tint i = 1;\n",
    "\t\twhile (n)\n",
    "\t\t{\n",
    "\t\t\tdata[i] = n % 10;\n",
    "\t\t\tn /= 10;\n",
    "\t\t\ti++;\n",
    "\t\t}\n",
    "\t\tvalid_len = i - 1;\n",
    "\t}\n",
    "\tBigNum operator+(BigNum n2) // 定义加法\n",
    "\t{\n",
    "\t\tint scale = 0; //进位\n",
    "\t\tBigNum ans;\n",
    "\t\tans.valid_len = max(n2.valid_len, valid_len);\n",
    "\t\tfor (int i = 1; i <= min(n2.valid_len, valid_len); i++) // 公共位加法\n",
    "\t\t{\n",
    "\t\t\tint ret = n2.data[i] + data[i] + scale;\n",
    "\t\t\tscale = ret / 10;\n",
    "\t\t\tret %= 10;\n",
    "\t\t\tans.data[i] = ret;\n",
    "\t\t}\n",
    "\t\tif (n2.valid_len > valid_len) // 剩余位加法\n",
    "\t\t{\n",
    "\t\t\tfor (int i = 1 + min(n2.valid_len, valid_len); i <= max(n2.valid_len, valid_len); i++)\n",
    "\t\t\t{\n",
    "\t\t\t\tint ret = n2.data[i] + 0 + scale;\n",
    "\t\t\t\tscale = ret / 10;\n",
    "\t\t\t\tret %= 10;\n",
    "\t\t\t\tans.data[i] = ret;\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t\telse if (n2.valid_len < valid_len) // 剩余位加法\n",
    "\t\t{\n",
    "\t\t\tfor (int i = 1 + min(n2.valid_len, valid_len); i <= max(n2.valid_len, valid_len); i++)\n",
    "\t\t\t{\n",
    "\t\t\t\tint ret = data[i] + 0 + scale;\n",
    "\t\t\t\tscale = ret / 10;\n",
    "\t\t\t\tret %= 10;\n",
    "\t\t\t\tans.data[i] = ret;\n",
    "\t\t\t}\n",
    "\t\t}\n",
    "\t\tif (scale > 0) // 处理最高位的进位\n",
    "\t\t{\n",
    "\t\t\tans.data[++ans.valid_len] += scale;\n",
    "\t\t}\n",
    "\t\treturn ans;\n",
    "\t}\n",
    "\tinline void print()\n",
    "\t{\n",
    "\t\tif (valid_len == 0)\n",
    "\t\t{\n",
    "\t\t\tprintf(\"0\");\n",
    "\t\t\treturn;\n",
    "\t\t}\n",
    "\t\tfor (int i = valid_len; i > 0; i--)\n",
    "\t\t{\n",
    "\t\t\tprintf(\"%d\", data[i]);\n",
    "\t\t}\n",
    "\t}\n",
    "};"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.10.2 (tags/v3.10.2:a58ebcc, Jan 17 2022, 14:12:15) [MSC v.1929 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
